Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Two-view “cylindrical decomposition” of binary images
2001
This paper describes the discrete cylindrical algebraic decomposition (DCAD) construction along two orthogonal views of binary images. The combination of two information is used to avoid ambiguities for image recognition purposes. This algorithm associates an object connectivity graph to each connected component, allowing a complete description of the structuring information. Moreover, an easy and compact representation of the scene is achieved by using strings in a five letter alphabet. Examples on complex digital images are also provided. © 2001 Elsevier Science Inc.
Text Compression Using Antidictionaries
1999
International audience; We give a new text compression scheme based on Forbidden Words ("antidictionary"). We prove that our algorithms attain the entropy for balanced binary sources. They run in linear time. Moreover, one of the main advantages of this approach is that it produces very fast decompressors. A second advantage is a synchronization property that is helpful to search compressed data and allows parallel compression. Our algorithms can also be presented as "compilers" that create compressors dedicated to any previously fixed source. The techniques used in this paper are from Information Theory and Finite Automata.
Using Induced Ordered Weighted Averaging (IOWA) Operators for Aggregation in Cross-Efficiency Evaluations
2014
This paper proposes an enhancement of the cross-efficiency evaluation through the aggregation of cross-efficiencies by using a particular type of induced ordered weighted averaging IOWA operator. The use of a weighted average of cross-efficiencies for the calculation of the cross-efficiency scores, instead of the usual arithmetic mean, allows us to introduce some flexibility into the analysis. In particular, the main purpose of the approach we present is to provide aggregation weights that reflect the decision maker DM preferences regarding the relative importance that should be attached to the cross-efficiencies provided by the different decision-making units. To do it, an ordering is to b…
Sudoku – A Language Description Case Study
2009
A complete language description includes the structure as well as constraints, textual representation, graphical representation, and behaviour (transformation and execution). As a case study in language description, we consider Sudoku as a language, where a Sudoku puzzle is an instance of the language. Thus we are able to apply meta-model-based technologies for the creation of a language description for Sudoku, including correctness checking of a puzzle, and solving strategies. We identify what has to be expressed and how this can be done with the technology available today.
Enumerable classes of total recursive functions: Complexity of inductive inference
1994
This paper includes some results on complexity of inductive inference for enumerable classes of total recursive functions, where enumeration is considered in more general meaning than usual recursive enumeration. The complexity is measured as the worst-case mindchange (error) number for the first n functions of the given class. Three generalizations are considered.
Binary jumbled string matching for highly run-length compressible texts
2012
The Binary Jumbled String Matching problem is defined as: Given a string $s$ over $\{a,b\}$ of length $n$ and a query $(x,y)$, with $x,y$ non-negative integers, decide whether $s$ has a substring $t$ with exactly $x$ $a$'s and $y$ $b$'s. Previous solutions created an index of size O(n) in a pre-processing step, which was then used to answer queries in constant time. The fastest algorithms for construction of this index have running time $O(n^2/\log n)$ [Burcsi et al., FUN 2010; Moosa and Rahman, IPL 2010], or $O(n^2/\log^2 n)$ in the word-RAM model [Moosa and Rahman, JDA 2012]. We propose an index constructed directly from the run-length encoding of $s$. The construction time of our index i…
Nondeterministic operations on finite relational structures
1998
Abstract This article builds on a tutorial introduction to universal algebra for language theory (Courcelle, Theoret. Comput. Sci. 163 (1996) 1–54) and extends it in two directions. First, nondeterministic operations are considered, i.e., operations which give a set of results instead of a single one. Most of their properties concerning recognizability and equational definability carry over from the ordinary case with minor modifications. Second, inductive sets of evaluations are studied in greater detail. It seems that they are handled most naturally in the framework presented here. We consider the analogues of top-down and bottom-up tree transducers. Again, most of their closure propertie…
Free boundary methods and non-scattering phenomena
2021
We study a question arising in inverse scattering theory: given a penetrable obstacle, does there exist an incident wave that does not scatter? We show that every penetrable obstacle with real-analytic boundary admits such an incident wave. At zero frequency, we use quadrature domains to show that there are also obstacles with inward cusps having this property. In the converse direction, under a nonvanishing condition for the incident wave, we show that there is a dichotomy for boundary points of any penetrable obstacle having this property: either the boundary is regular, or the complement of the obstacle has to be very thin near the point. These facts are proved by invoking results from t…
A Motzkin filter in the Tamari lattice
2015
The Tamari lattice of order n can be defined on the set T n of binary trees endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we restrict our attention to the subset M n of Motzkin trees. This set appears as a filter of the Tamari lattice. We prove that its diameter is 2 n - 5 and that its radius is n - 2 . Enumeration results are given for join and meet irreducible elements, minimal elements and coverings. The set M n endowed with an order relation based on a restricted rotation is then isomorphic to a ranked join-semilattice recently defined in Baril and Pallo (2014). As a consequence, we deduce an upper bound for the rotation distan…
Process specification and verification
1996
Graph grammars provide a very convenient specification tool for distributed systems of processes. This paper addresses the problem how properties of such specifications can be proven. It shows a connection between algebraic graph rewrite rules and temporal (trace) logic via the graph expressions of [2]. Statements concerning the global behavior can be checked by local reasoning.